#include<iostream>
using namespace std;
struct Node {
	int val;
	Node* next;
	Node* prev;
	Node(int val_) :val(val_), next(NULL), prev(NULL) {

	}
};

class List {
private:
	Node head;
public:
	List():head(-1){

	}
	~List() {
		//
	}

	void insert(Node* node) {
		if (node == NULL) return;
		if (head.next == NULL) {
			node->next = node;
			node->prev = node;
		}
		else {
			auto last = head.next->prev;
			last->next = node;
			node->prev = last;
			node->next = head.next;
			head.next->prev = node;
		}
		head.next = node;
	}

	void print() {
		auto node = head.next;
		while (node != NULL) {
			cout << node->val << " ";
			node = node->next;
			if (node == head.next)
				break;
		}
	}
};

int main() {
	List list;
	list.insert(new Node(1));
	list.insert(new Node(2));
	list.insert(new Node(3));
	list.insert(new Node(4));
	list.print();

}

